/**
 * extended apache commons-lang StringUtils
 * 
 * functions below is appended:
 * <ul>
 * <li> LCS(String, String) : an implemetation LCS </li>
 * </ul>
 */
@Grab(group='commons-lang', module='commons-lang', version='2.4')
import org.apache.commons.lang.StringUtils

/**
 * find longest common string of two strings
 * we treat the string like char array
 *
 * Memory	: O(arrayA.size * arrayB.size)
 * Time		: O(arrayA.size * arrayB.size)
 *
 * @return 
 */
org.apache.commons.lang.StringUtils.metaClass.static.LCS = { A, B ->

	int m = A.size()	//A,y,j,m
	int n = B.size()	//B,x,i,n
	int min = Math.min(m, n)
	assert min < (1<<14)

	//r[i][j] = [01]{30}[01]{2}
	//first 30 bits store the length, and last 2 bits store previous cell info
	//Last two bits mapping: [00: 'X', 01: 'L', 10: 'T', 11: 'B']
	short[][] r = new short[n][m]
	
	//initialize r[0][j] and r[i][0] first, will get better performance. 
	//(reduce the if-else branches in loops)
//	r[0][0] = [
//		len	: (A[0] == B[0])?1:0,
//		pre	: 'X'
//	]
	r[0][0] = (((A[0] == B[0])?1:0)<<2)
	
	//first row
	for (int j = 1; j < m; j ++) {
		if (A[j] == B[0]) {
//			r[i][j] = [
//				len	: 1,
//				pre	: (r[i][j-1].len == 0)?'X':'L'
//			]
			r[0][j] = (1<<2)|(((r[0][j-1]>>2) == 0)?0:1)
		} else {
//			r[i][j] = [
//				len	: r[i][j-1].len,
//				pre	: 'L'
//			]
			r[0][j] = ((r[0][j-1]>>2)<<2)|1
		}
	}
	
	//first column
	for (int i = 1; i < n; i ++) {
		if (A[0] == B[i]) {
//			r[i][j] = [
//				len	: 1,
//				pre	: (r[i-1][j].len == 0)?'X':'T'
//			]
			r[i][0] = (1<<2)|(((r[i-1][0]>>2) == 0)?0:2)
		} else {
//			r[i][j] = [
//				len	: r[i-1][j].len,
//				pre	: 'T'
//			]
			r[i][0] = ((r[i-1][0]>>2)<<2)|2
		}
	}
	
	for (int k = 0; k < m+n-1; k ++) {
		for (int i = Math.max(1, k-m+1); i <= Math.min(k-1, n-1); i ++) {
			int j = k-i;// i > 0 && j > 0
			if (A[j] == B[i]) {
//				r[i][j] = [
//					len	: r[i-1][j-1].len+1,
//					pre	: 'B'
//				]
				r[i][j] = (((r[i-1][j-1]>>2)+1)<<2)|3
			} else {
				if ((r[i-1][j]>>2) >= (r[i][j-1]>>2)) {
//					r[i][j] = [
//						len	: r[i-1][j].len,
//						pre	: 'T'
//					]
					r[i][j] = ((r[i-1][j]>>2)<<2)|2
				} else {
//					r[i][j] = [
//						len	: r[i][j-1].len,
//						pre	: 'L'
//					]
					r[i][j] = ((r[i][j-1]>>2)<<2)|1
				}
			}
		}
	}
	
	println "-----------FOR DEBUG-------------------"
	print "\t\t"
	for (int j = 0; j < m; j ++) print "${A[j]}[${j}]\t"
	println ""
	for (int i = 0; i < n; i ++) {
		print "${B[i]}[${i}]\t"
		for (int j = 0; j < m; j ++) {
			print "${r[i][j]>>2},${['X','L','T','B'][r[i][j]%4]}\t\t"
		}
		println ""
	}
	println A
	println B
	println "-----------ENDOF DEBUG-------------------"

	//create lcs result
	def tmpA = [], tmpB = []
	def x = n-1, y = m-1
	def count = r[n-1][m-1]>>2
	while (count > 0) {
		if (A[y] == B[x]) {
			tmpA.add(y)
			tmpB.add(x)
			count --
		}

		if (r[x][y]%4 == 0) {	//'X'
			break;
		} else if (r[x][y]%4 == 1) {	//'L'
			y--
		} else if (r[x][y]%4 == 2) {	//'T'
			x--
		} else {	//'B'
			x--
			y--
		}
	}
	return [length: r[n-1][m-1]>>2, subA: tmpA.reverse(), subB: tmpB.reverse()]
}

//--------------------------------------------------------------------------
// function
//--------------------------------------------------------------------------
def printLines(array, name, s, e) {
//	println "------${name} ${s}, ${e}"
	if (e > s) {
		println "<<< ${name} (line ${s+1} ~ line ${e})"
		for (int j = s; j < e; j ++) println array[j]
		println ">>> ${name}"
	}
}

def printResult(A, nameA, B, nameB, R) {

	def blocks = [0]
	
	for (int i = 1; i < R.subA.size(); i ++) {
		if (R.subA[i] - R.subA[i-1] > 1 || R.subB[i] - R.subB[i-1] > 1) {
			blocks.add(i)
		}
	}
	blocks.add(R.subA.size())
	
	int s, e
	for (int i = 0; i < blocks.size()-1; i ++) {
		if (i == 0) {
			printLines(A, nameA, 0, R.subA[0])
			printLines(B, nameB, 0, R.subB[0])
		} else {
			printLines(A, nameA, R.subA[blocks[i]-1]+1, R.subA[blocks[i]])
			printLines(B, nameB, R.subB[blocks[i]-1]+1, R.subB[blocks[i]])
		}
		
		s = R.subA[blocks[i]]
		e = R.subA[blocks[i+1]-1]
		for (int j = s; j <= e; j ++) println A[j]
	}
	//print tails
	printLines(A, nameA, R.subA[blocks[blocks.size()-1]-1]+1, A.size())
	printLines(B, nameB, R.subB[blocks[blocks.size()-1]-1]+1, B.size())
}

//------------------------------------------------------------
// TEST
//------------------------------------------------------------
long start = System.currentTimeMillis()
//def A = new File(/D:\develop\Java\groovy4u\test\Test.v1.java/).getText().split("\r\n")
//def B = new File(/D:\develop\Java\groovy4u\test\Test.v2.java/).getText().split("\r\n")

//def A = new File(/D:\develop\Java\groovy4u\test\SearchUtils.v1.java/).getText().split("\r\n")
//def B = new File(/D:\develop\Java\groovy4u\test\SearchUtils.v2.java/).getText().split("\r\n")

//def A = new File(/D:\develop\Java\groovy4u\test\large.v1.java/).getText().split("\r\n")
//def B = new File(/D:\develop\Java\groovy4u\test\large.v2.java/).getText().split("\r\n")

//def A = ("ABCBDAB"*1).toCharArray()
//def B = ("BDCABA"*1).toCharArray()

//def A = ("ABCBDAB"*1).toCharArray()
//def B = ("ABDCABA"*1).toCharArray()

//def A = ("ABDCABA"*1).toCharArray()
//def B = ("ABCBDAB"*1).toCharArray()

def A = ("BDCABA"*1).toCharArray()
def B = ("ABCBDAB"*1).toCharArray()

def R = org.apache.commons.lang.StringUtils.LCS(A,B)
println "${System.currentTimeMillis() - start} ms"
println R
printResult(A, "A", B, "B", R)